1. Conventional Video Compression
Modern electronic data processing systems are now often used not only for conventional numeric and text processing tasks, but also for processing data corresponding to visual images. As such, many modern computer and telecommunications systems have "multimedia" capabilities, where the data processed and communicated includes video images either generated by a computer or digitized from a conventional video camera.
The capacity required to communicate video images on a real-time basis is huge, however, when measured against modern capabilities. For example, a single video image (i.e., frame) displayed by a rectangular array of picture elements ("pixels") arranged in 640 rows by 800 columns, with the color of each pixel represented by twenty-four digital bits, would require over 1.52 million bytes (1500 kbytes) of digital memory to store all information in the frame. While this memory requirement for a single video frame is large, digital storage of a series of frames, such as a motion picture, will quickly consume the disk storage capacity of even high-end computers and workstations.
The large amount of digital data necessary to represent a video frame not only impacts computer storage requirements, but limits the rate at which conventional systems can communicate motion pictures. Considering that conventional high-speed digital communication channels have a bandwidth of on the order of from 40 to 80 MHz, it becomes quite apparent that conventional motion pictures of thirty frames per second, with 1500 kbytes of digital information per frame, cannot be fully transmitted in real-time over state of the art digital communications systems.
In response to these limitations on the ability of modern computer systems to store and communicate video information, various types of data compression techniques have been developed in recent years. Conventional data compression techniques are generally referred to as of either "lossless" or "lossy", depending upon whether data is discarded in the compression process.
A survey of conventional lossless data compression is provided in Simon, "Lossless Compression: How it Works", PC Magazine (Jun. 29, 1993), pp. 305-13. Examples of conventional lossless data compression techniques include Huffman encoding, Fano-Shannon encoding, and arithmetic encoding, as well as dynamic variations of the Huffman and Fano-Shannon probabilistic encoding techniques. In general, lossless compression techniques are primarily used to compress entered data such as data generated from data processing operations, rather than sampled data representative of analog video or audio signals, as decompression will reproduce all bits of the original compressed data stream.
Lossy data compression techniques, in contrast, provide additional data compression efficiency over lossless data compression, as some amount of data is discarded in these techniques. As a result, lossy data compression techniques are generally used on sampled data, as some amount of inaccuracy relative to the true input data is tolerable; lossy data compression is, of course, inappropriate for use on entered data streams such as those produced by a data processing operation. Accordingly, lossy data compression techniques are widely used in the field of compression of video and motion picture images to obtain a high degree of compression, as some inaccuracy may be tolerated. A survey of conventional lossy data compression techniques may be found at Simon, "How Lossy Data Compression Shrinks Image Files", PC Magazine (July 1993), pp. 371 et seq.
A popular conventional lossy data compression technique is referred to as the JPEG (Joint Photographic Experts Group) method. A description of this technique may be found in Barnsley and Hurd, Fractal Image Compression (AK Peters, Ltd., 1993), pp. 219-228. The JPEG compression method initially divides the image into blocks of pixels, and a Discrete Cosine Transform (DCT) is performed on each pixel block, producing a representation of the block as coefficients corresponding to frequencies and amplitudes, rather than corresponding directly to color information. These coefficients are then quantized, or rounded off, and a difference algorithm is performed over all quantized blocks in the image, in a selected scan order. This difference algorithm subtracts a DC term corresponding to the mean pixel value of a block, from the DC term of the preceding block. The difference coefficients are then scanned in a different order, such as a zig-zag order, and the non-zero coefficients (i.e., blocks in which a difference from the preceding block occurred) are coded to indicate the number of preceding zero coefficients (i.e., the number of pixel blocks in which no change occurred) and also the value of the non-zero difference. Lossless compression is then often applied to the coded result to further compress the data. Decompression is performed by reversing the compression process, producing the displayable image.
While the JPEG conventional video image compression technique is useful in obtaining high degrees of compression, it has been found that JPEG compression is incapable of being used in a real-time fashion for a motion picture. This is because the time generally required to perform the JPEG decompression of a motion picture frame exceeds the display time for the frame ( 1/30 second), and as a result the motion picture image cannot be decompressed for real-time display. Temporally accurate display of a motion picture compressed according to these techniques, thus requires the decompression and display to be done in two steps, with the decompressed motion picture stored on video tape or another medium from which the motion picture can be played with the proper time base.
Another conventional method of lossy video image compression referred to as Recursive Vector Quantization (RVQ) quantizes the pixel blocks directly, without a DCT or other transform, according to a set of selected reference tiles. See Simon, July 1993, op. cit. The reference tiles are selected according to an iterative technique, based upon the accuracy of the results relative to the original image. As noted in the Simon article, compression according to the RVQ method is computationally intense and complex, but decompression can be done quite rapidly.
Another type of conventional lossy video image compression techniques is referred to as fractal compression. As is well known in the art, a fractal is a mathematical image object that is self-similar, in that the image can be represented in terms of other pieces of the image. In fractal image compression, the input image is similarly divided into pixel groups, or tiles. Each tile is then approximated by a transformation (contractive, rotational, or both) of one or more other reference regions of the image. The compressed image thus consists of a full representation of the reference region, plus the transformation operators for each of the tiles. Each tile of the image is decompressed by performing a transformation of the reference region using the stored transformation operator for that tile. Detailed descriptions of conventional fractal image compression techniques and systems for performing the same may be found in Barnsley & Hurd, Fractal Image Compression (AK Peters, Ltd., 1993), in U.S. Pat. No. 4,941,193, and in U.S. Pat. No. 5,065,447.
2. Frequency and Time Windowing Functions
By way of further background, the field of wavelet analysis has recently become popular in the analysis of the time and frequency response and behavior of signals. The following section of this application is intended to provide a theoretical background for wavelet analysis techniques in order to both convey the state of the art in wavelet analysis, and also to provide the necessary background for the person of ordinary skill in the art to fully appreciate the present invention.
In the general sense, wavelet analysis is concerned with performing time-frequency localization of the signal to be analyzed (i.e,. the "input signal"). Time-frequency localization refers to the analysis of a portion of the frequency spectrum of the input signal over a selected time window. As will become apparent from the description in this specification, time-frequency localization of an input signal enables data processing techniques to be applied to the signals for a wide range of purposes.
a. Conventional Analog Filtering
In the time domain, frequency-windowing is done by convolving a time-domain window filter function with the input signal; in the frequency domain, the frequency-windowing is done by multiplying the spectrum of the input signal with the frequency-domain transfer function of the filter function. Typical filter functions include low-pass filters (e.g., the Shannon sampling function) and band-pass filters. Through use of such filters, a bandwidth limited signal f.sub..OMEGA. (t) (i.e., zero amplitude for all frequencies above a limit .OMEGA.) may be decomposed into the sum of a low-frequency component with a series of non-zero frequency bands. An expression for such a decomposition is as follows: EQU f.sub..OMEGA. (t)=f.sub..OMEGA.,.omega..sbsb.0 (t)+g.sub..OMEGA.,1 (t)+ . . . +g.sub..OMEGA.,N (t) [1]
where f.sub..OMEGA.,.omega.0 is the low-pass filtered (.omega.&lt;.omega..sub.0) component of the input signal f.sub..OMEGA. (t), where g.sub..omega.,i (t) is the band-pass filtered signal for the ith frequency band, and where .omega..sub.N =.OMEGA.. An ideal low-pass filtered component f.sub..OMEGA., .omega.0 corresponds to the time-domain convolution of the well-known Shannon sampling function with the input signal. Ideal band-pass filtering may be performed by time-domain convolution of a filter function of the type: ##EQU1## with the time-domain input signal, .omega..sub.n and .omega..sub.n-1 being the upper and lower limits of the frequency band.
Each of the low-pass and band-pass filter functions provide ideal frequency localization of the input signal f.sub..OMEGA. (t), such that each expression f.sub..OMEGA.,.omega.0 and g.sub..OMEGA.,i (t) provide precise information regarding the frequency spectrum of input signal f.sub..OMEGA. (t) within its respective frequency band. However, the time localization provided by this decomposition is quite poor, as these filters do not provide very precise information about when (in the time domain) a signal behaves differently within certain frequency ranges. As many important real-world signals include brief periods of time of rapid transient change, analysis of signals decomposed in this manner will not be able to account for the time at which such transient behavior occurs. For signal analysis where time localization is important, conventional Fourier analysis techniques therefore falls short of the need.
b. Time and Frequency Windowing
Certain conventional signal analysis techniques have addressed this problem by time-windowing the input signal, thus allowing time-localization as well as frequency localization. According to these techniques, a window function h(t) is applied to the input signal f(t) to window the input signal near a specified point in time t=b. This windowing may be considered by the integral transform: ##EQU2## where the bar over the function h(t-b) denotes complex conjugation. For a real-valued even windowing function h(t), this windowing process corresponds to convolution, allowing treatment of the windowing function h(t) as a filter. For example, if h(t) is the Shannon sampling function, the windowing process of the above equation will apply a low-pass filter to the input signal. However, it has been observed that the slow decay of the Shannon sampling function over time results in a very imprecise time-domain windowing operation.
Those windowing functions h(t), for which the square of the magnitude have finite first and second moments and finite energy, (i.e., that decay sufficiently rapidly at infinity) will produce a time-window having a "center" t* and a "radius" .DELTA..sub.h. The center t* may be calculated as a mean value, while the radius may be calculated as the standard deviation of the windowing function around the mean t*. For a windowing function of radius .DELTA..sub.h, the width of the time-window will be 2.DELTA..sub.h, commonly referred to as the RMS duration of the windowing function h(t). In the frequency domain, if the square of the magnitude of the Fourier transform h(.omega.) of the windowing function h(t) has finite first and second moments, the frequency domain windowing function h(.omega.) will have a center .omega.* and a width 2.DELTA..sub.h, calculated in a manner similar to the mean and standard deviation (doubled) of the frequency domain function h(.omega.); the width 2.DELTA..sub.h is usually called the RMS bandwidth of the windowing function h(t). If the RMS duration .DELTA..sub.h is finite, then the time-domain windowing function h(t) is a time-window; similarly, if the RMS bandwidth 2.DELTA..sub.h is finite, the frequency-domain windowing function h(.omega.) is a frequency window.
Referring back to the ideal low-pass and band-pass filter time-domain functions noted above, it will be readily apparent that their first moment is infinite, meaning that neither of these ideal filter functions can serve as time windows if used as windowing functions h(t). However, the frequency domain representations of the ideal low-pass and band-pass filter functions have finite RMS bandwidth 2.DELTA..sub.h, so that these filters provide ideal frequency-localization as is evident from their ideal nature.
As discussed above, accurate analysis of real-world signals containing transient behavior requires both time-localization and frequency-localization. The Uncertainty Principle has identified those windowing functions h that provide both time windowing and frequency windowing as those functions that satisfy the following inequality: EQU .DELTA..sub.h .DELTA..sub.h .gtoreq.1/2 [5]It has also been previously found that the only types of windowing functions h(t) that achieve the lower bound of the Uncertainty Principle are those of the form: EQU h(t)=ce.sup.jat e.sup.(t-b).spsb.2.sbsp./4.alpha. [ 6]
for some constants a, b, c and .alpha. with .alpha.&gt;0 and c.noteq.0.
Further indication of the presence of a time-frequency window by any windowing function h(t) may be obtained through the Parseval identity. The generalized windowing function h(t) noted above corresponds to: ##EQU3## With reference to the left side of equation [6], the time window is given by: EQU [b+t*-.DELTA..sub.h, b+t*+.DELTA..sub.h ] [8]
such that the time window that is centered on t.dbd.t* is shifted by the parameter b; the time window also has a radius of .DELTA..sub.h in the time dimension. Similarly, with reference to the right-hand side of equation [6], the frequency window is given by: EQU [.omega.*-.DELTA..sub.h, .omega.*+.DELTA..sub.h ] [9]
and is thus centered at .omega..dbd..omega.* with width 2.DELTA..sub.h. FIG. 1a illustrates the location of time-frequency window 2 of equation [6] in a time-frequency coordinate system.
For causal real-valued window functions, where: EQU h(-.omega.)=h(.omega.)
the function .vertline.h(.omega.).vertline. is an even function, so that the center .omega.* is located at .omega.=0 and the frequency window of equation [9] becomes EQU [-.DELTA..sub.h, .DELTA..sub.h ] [10]
However, while the time-frequency window of the filtering function h(t) may be moved along the time axis of FIG. 1a by changing the value of b, the window is fixed in frequency at the center frequency .omega.* or, in the case of real-valued even functions as noted above relative to equation [10], is fixed at a center frequency .omega.*=0, as shown in FIG. 1b. This fixation in frequency of the time-frequency window in limits the usefulness of the windowing process of equation [3].
c. The Short-Time Fourier Transform (STFT)
Rudimentary Fourier theory indicates that translation in the time-domain corresponds to a phase-shift in the frequency domain, and conversely that a phase-shift in the time-domain corresponds to a translation in the frequency domain. Accordingly, a phase shift in the windowing process of equation [3] should allow for sliding of the frequency window along the frequency-axis.
Considering a real-valued window function .phi.(t) which serves as a low-pass filter (i.e., .phi.(.omega.=0)=1), and for which .phi.(t), .vertline.t.vertline..sup.1/2 .phi.(t) and t.phi.(t) are in L.sup.2, the short-time Fourier transform of .phi.(t) is defined by: ##EQU4## for f .epsilon. L.sup.2. The short-time Fourier transform (STFT) of equation [11] is also referred to in the literature as the Gabor transform. Applying the Parseval identity results in the following expression for the STFT, from which the center and radii of the time and frequency windows are apparent: ##EQU5##
The short-time Fourier transform of equations [11] and [12] provide the improvement over the simple time-windowing process of equation [3] in that the frequency window function .phi.(.omega.) is able to slide along the frequency axis. The frequency window for a windowing function .phi.(.omega.) that otherwise (i.e., for .xi.=0) has its center .omega.* at .omega.=0, is now localized to frequencies near .omega.=.xi.: EQU [.xi.-.DELTA..sub..phi., .xi.+.DELTA..sub..phi. ] [13]
Similarly, where the center t* of the windowing function .phi.(t) is also otherwise (b=0) located at the origin, the time window is now localized near t=b as follows: EQU [b-.DELTA..sub..phi., b+.DELTA..sub..phi. ] [14]
The STFT thus allows for sliding of the time-frequency localization windows both in time and in frequency, merely by changing the values of the phase-shift factors b, .xi., respectively. FIG. 1c illustrates the position in time-frequency space of two time-frequency windows 5.sub.0, 5.sub.1, having phase-shift factors (b.sub.0, .xi..sub.0), (b.sub.1, .xi..sub.1), respectively. As a result, the STFT allows the lowpass window function to perform bandpass filtering by changing the value of .xi.. However, as is evident in FIG. 1c, the widths of the windows are invariant with changes in time-shift factor b or frequency-shift factor .xi.. Accordingly, while analysis is improved through use of the short-time Fourier transform, inaccuracies due to undersampling have been observed for those transient periods of time in which rapid changes (i.e., amplitudes over a wide range of frequencies) exist. Accordingly, not only is the ability to slide the localization windows in both time and frequency desired, but it is also desirable to allow for scaling of the window widths as a function of time or frequency.
3. Wavelet Analysis
a. Theory
Wavelet analysis techniques address the need for time-frequency localization windows of flexible size, primarily by introducing a scale parameter that is mapped to the frequency variable. As a result, the scale parameter will change the widths of the windows as a function of frequency, thus changing the aspect ratio of the windows with changes in frequency. Since the Uncertainty Principle requires the area of the windows to remain above a certain value, the time window width decreases and the frequency window width increases proportionally as the center frequency .xi. increases. The narrowing of the time window and widening of the frequency window for high frequency environments more precisely detects and analyzes these high frequency portions of input signals.
The basic wavelet transform is known as the integral wavelet transform, or IWT. The IWT includes a scale parameter a in its definition as follows: ##EQU6## As such, the window function .psi. narrows with changing values of the scale parameter a, such that the time width of .psi. decreases with decreasing a. The windowing function .psi.(t) used in the IWT of equation [15] is to be real-valued as before, but the IWT constraints also require .psi.(t) to be a bandpass filter rather than a low pass filter, such that its Fourier transform .psi.(.OMEGA.=0)=0, stopping at least zero frequency components of the signal. Since the windowing function .psi.(t) is real-valued, its Fourier transform .psi.(.omega.) satisfies: EQU .psi.(-.omega.)=.psi.(.omega.) [16]
so that .vertline..psi.(.omega.) .vertline. is an even function. Because only nonnegative frequencies are of interest, and since .psi.(t) is a band-pass filter, the Fourier transform .psi.(.omega.) need only be considered as a frequency window in the frequency domain [0, .infin.), with the centers and widths of the frequency window function .psi.(.omega.) being modified as a result. For a windowing function .psi.(t) in L.sup.2, for which .vertline.t.vertline..sup.1/2 .psi.(t) and t.psi.(t) are also in L.sup.2 such that .psi.(t) is real-valued, and where .psi.(.omega.=0)=0, the one-sided (i.e., nonnegative) frequency window center .omega.*.sub.+ as a function on the domain [0, .infin.) is defined as: ##EQU7## and the one-sided radius of .psi.(.omega.) is defined as: ##EQU8##
This allows the generation of an integral wavelet transform (IWT) using a normalization factor a.sup.-1/2 based upon the scale parameter a, which scales the time-width of the window as a function of frequency. For a windowing function .psi.(t) that satisfies the conditions for equations [17] and [18] above, the IWT is defined as follows: ##EQU9## For the IWT of equation [19], the bandpass window-function .psi.(t) is commonly referred to as the analyzing wavelet.
As is known in the wavelet analysis field, and given the foregoing discussion, it is important that the integral wavelet transform W.sub..psi. allows for frequency localization where the width of the time window is mapped to the frequency domain, and in which the frequency window can slide along the frequency axis. For finite-energy real-valued input signals f(t), and since .psi.(t) is real, the following relationship holds: EQU f(-.omega.)e.sup.jb.omega. .psi.(-a.omega.)=f(.omega.)e.sup.-jb.omega. .psi.*a.omega.) [20 ]
Through the Parseval identity, one can then derive the IWT as follows: ##EQU10## for all f .epsilon. L.sup.2.sub.R, where .omega..sub.+ * is the one-sided center of .psi.(.omega.) on the domain [0, .infin.) , and where .eta. is defined as follows: EQU .eta.(.omega.):=.psi.(.omega.+.omega..sub.+ *) [22]
As noted above, it is desirable to map the scale parameter a to the frequency at which the time-frequency window is to be localized. Accordingly, the scale parameter a is mapped to the shift frequency parameter .xi. as follows: ##EQU11## for some c&gt;0, where c is a calibration constant. Substituting for the scale parameter a defines the IWT as follows: ##EQU12## It is convenient to set c.dbd..omega..sub.+ *, so that: ##EQU13## This produces a frequency window .eta.(a(.omega.-.xi.)) that slides along the frequency axis with the value of .xi., having a range: ##EQU14## The width of this window thus increases at higher frequencies .xi., as reflected in smaller values of the scale parameter a. In terms of the scale parameter a, the width of the frequency-window is as follows: ##EQU15## where the frequency shifting term .xi.=.omega..sub.+ */a, such that the frequency-width of the frequency window increases with increasing frequency .xi. (decreasing values of a). Along the time-axis, the time window of the IWT of equation [19] is given by: EQU [b+at*-a.DELTA..sub..psi., b+at*+a.DELTA..sub..psi. ] [28]
As a result, the width of this time-window is 2a.DELTA..sub..psi., which decreases at higher frequencies .xi. (and lower values of a), and which increases at lower frequencies .xi.. For the transform of equation [15], FIG. 1d illustrates three time-frequency windows 6.sub.0, 6.sub.1, 6.sub.2, with varying translation factor pairs (b.sub.0, .xi..sub.0), (b.sub.1, .xi..sub.1), (b.sub.2, .xi..sub.2), respectively. As is evident in FIG. 1d, both the time-width and frequency-width of windows 6 vary with varying shift frequency .xi., such that the time-width decreases and the frequency-width increases with increasing .xi..
Accordingly, it should now be apparent to those in the art that wavelet analysis is capable of providing increased accuracy analysis of signals, particularly those including transient components, considering that, for higher frequency analysis, the width of the time window decreases and the width of the frequency window increases. This ensures adequate sampling of the input signal function, and also allows for determination of the exact time in the signal at which the transient event occurred.
As is known in the art of wavelet analysis, however, the definition of the proper wavelet function .psi.(t) is of great importance. Various specified analyzing functions have been used in wavelet analysis, with the selection of the function made according to computability, or according to attributes of the signal under analysis.
Prior Wavelets
Wavelet signal analysis has been applied to signals produced in seismic exploration for oil and gas, as described in U.S. Pat. No. 4,599,567. This reference describes a wavelet analysis technique using Morlet's wavelet as the analyzing wavelet. Morlet's wavelet is a sinusoid limited by a Gaussian probability envelope to a finite duration; the envelope may or may not be skewed toward either the leading or lagging edge of the time-domain envelope of the wavelet, as desired for the type of signal under analysis. This reference also discloses circuitry for performing the wavelet analysis of an incoming signal using such analyzing wavelet.
Another finite duration analyzing wavelet was proposed by Yves Meyer. This analyzing wavelet is substantially a finite duration uniform magnitude level over the wavelet window, analogous to the Shannon sampling function.
Other wavelets have been proposed which are not expressible by a mathematical formula, but instead are utilized as numeric wavelets. These wavelets include the Battle-Lemanne wavelet, which is a spline function of infinite duration, and the Daubechies wavelet, which is a fractal wavelet of finite duration. The lack of explicit formulae for these wavelets limit their applicability for rapid and accurate computer implementation of the wavelet analysis technique in computer hardware.
Another previously published wavelet is the Chui-Wang wavelet, which is a wavelet of finite duration but which may be expressed in an explicit formula.
The support for each of the prior wavelets noted above is over an unbounded interval. However, since real-world problems require the application of the wavelets to bounded intervals, wavelet analysis of input signals using these prior wavelets result in errors of the type commonly referred to as "boundary effects".
FIG. 2 graphically illustrates the reason for boundary effects arising from such conventional wavelets. Conventional wavelet 7 illustrated in FIG. 2a is first-order spline-wavelet that is based on a function .psi. having moments with the following properties (for i=0, 1, . . . m-1, and some m.gtoreq.1): ##EQU16## where a, b are scaling parameters as discussed above. The conventional wavelet 7 of FIG. 2a is not orthogonal over a bounded interval [c, d], however, meaning that: ##EQU17## for all integers i&gt;0.
FIG. 2 graphically illustrates the performance of the IWT using wavelet 7 having the above noted properties at a point in the time series which happens to be at or near the boundary of an interval [c, d]. Data points f.sub.2, f.sub.3, f.sub.4 correspond to input signal samples within the interval, which are plotted against wavelet 7 in FIG. 2; in this example, for purposes of explanation, the input signal sample data closely matches the shape of wavelet 7 within the interval [c, d]. The position of wavelet 7 corresponds to the position, in performing the IWT, of the sample point of interest at the boundary value t=a. Since wavelet 7 at this position requires support outside of the interval [c, d] for which input signal data exists, the zero values that must be assumed for the data points f.sub.0, f.sub.1 outside of interval [c, d] necessarily fail to match wavelet 7. This will result in an non-zero result for the IWT, even where the input data signal within the interval [c, d] exactly matches wavelet 7. As is well known in the field of signal processing, this inaccuracy due to wavelet 7 requiring support outside of the bounded interval [c, d] is made manifest by boundary effects at the edges of the bounded interval, since the unbounded wavelet 7 fails to accurately represent the series of actual input signal sample data.
In the field of video image compression and analysis, boundary effects greatly affects the quality of the image displayed after compression and decompression. This is because the boundary effects will appear as false image data at the edges of pixel blocks corresponding to bounded intervals, and also at the edges of the image (even if no subdivision of the image is performed). The inaccuracies due to boundary effects also limit the ability to magnify an image when displayed, considering that the magnification will make the boundary effect errors to become even more visible.
c. The Boundary-Spline-Wavelet
By way of further background, a bounded interval wavelet is described in Chui and Quak, "Wavelets on a Bounded Interval", Numerical Methods of Approximation Theory, Volume 9 (Dec. 1992), pp. 53-75, incorporated herein by this reference. This wavelet, which has an explicit formula, is not only a function of the time variable t, but is also a function of the position of the sample within the interval [c, d], so as to account for boundary effects. In effect, sample locations near the boundaries of the interval will correspond to different wavelet shapes than will sample locations within the interval that are away from the boundaries. Boundary effects are eliminated as the boundary wavelets do not require support outside of the interval.
Referring now to FIGS. 3a through 3d, an exemplary set of four first-order wavelets 8 according to the Chui-Quak boundary-spline-wavelet approach are illustrated. FIG. 3a illustrates the shape of "boundary" wavelet 8.sub.a for a sample location near the boundary t.dbd.a of the interval [a, b], while FIG. 3d illustrates the shape of boundary wavelet 8.sub.b for a sample location near the boundary t.dbd.b of the interval [a, b]. FIGS. 3b and 3c each illustrate the shape of "inner" wavelets 8.sub.i for sample locations within the interval [a, b] away from the boundaries. As is evident from FIGS. 3a through 3d, boundary wavelets 8a, 8b, have different shapes than inner wavelets 8.sub.i (which have the same shape as one other). As is further evident from FIGS. 3a through 3d, neither inner wavelets 8.sub.i nor boundary wavelets 8.sub.a, 8.sub.b require support outside of the interval [a, b], or: ##EQU18## for i=0, 1, . . . , m-1, and for some m.gtoreq.0, for the entire set of wavelets 8 of FIGS. 3a through 3d. Accordingly, application of the set of boundary-spline-wavelets 8 to actual real-world data, for which the time interval is necessarily bounded, will not produce boundary effect artifacts.
Other boundary-wavelets are known, as described in Daubechies, "Two recent results on wavelets: Wavelet bases for the interval and biorthogonal wavelet diagonalizing the derivative operator", Recent Advances in Wavelet Analysis, Schumaker and Webb, ed. (Academic Press, 1993), pp.237-58. These wavelets are not spline functions, and do not have explicit formulae. As a result, it is believed that these wavelets are of limited effectiveness in video image compression and decompression.
4. Objects of the invention
It is therefore an object of the present invention to apply wavelet analysis tools to the task of video image compression for storage and transmission.
It is a further object of the present invention to provide an apparatus for performing video image compression according to a selected wavelet.
It is a further object of the present invention to provide an apparatus for receiving a compressed video image and to decompress the same for real-time playback of the stored or communicated video image information.
It is a further object of the present invention to provide such a method of compression and decompression such that the compressed image may be played locally at real-time.
It is a further object of the present invention to provide such a system and method which allows for high accuracy magnification of the decompressed image, with much reduced incidence of edge effects.
It is a further object of the present invention to provide such a system and method which provides a high degree of compression.
It is a further object of the present invention to provide such a system and method which can utilize dynamic compression on a frame-by-frame basis, such that high frequency frames may be compressed to different ratios than low frequency frames.
It is a further object of the present invention to provide such a system and method which facilitates interactive display of a motion image, including insertion, editing and repetitive display.
It is a further object of the present invention to provide such a system and method which provides the ability for slow display systems to skip certain frames so that a motion picture can be displayed on a real-time basis by such slower systems, although with fewer frames per second.
It is a further object of the present invention to provide such a method and system which allows for division of an image into several portions for purposes of compression and communication or storage, with subsequent display of the full image after decompression.
It is a further object of the present invention to provide such a method and system which allows for higher lossy compression ratios by further quantization, as useful in compressing and decompressing high-quality 24-bit still images.
Other objects and advantages will be apparent to those of ordinary skill in the art having reference to the following specification, together with its drawings.